package william.string;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZhangShenao
 * @date 2024/2/22
 * @description <a href="https://leetcode.cn/problems/valid-parentheses/">...</a>
 */
public class Leetcode20_有效的括号 {
    /**
     * 借助栈实现
     * 遍历字符串,如果遇到左括号,则直接压栈;如果遇到右括号,则将栈顶的左括号弹栈,并判断该对括号是否匹配
     * 当字符串变量完成,判断栈是否为空
     */
    public boolean isValid(String s) {
        //边界条件校验
        if (s == null || s.isEmpty()) {
            return true;
        }

        //借助一个栈
        Deque<Character> stack = new LinkedList<>();

        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //如果遇到左括号,直接压栈
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
                continue;
            }

            //如果遇到右括号,将栈顶的左括号弹栈,并判断是否匹配
            if (c == ')' && (stack.isEmpty() || stack.pop() != '(')) {
                return false;
            }
            if (c == '}' && (stack.isEmpty() || stack.pop() != '{')) {
                return false;
            }
            if (c == ']' && (stack.isEmpty() || stack.pop() != '[')) {
                return false;
            }
        }

        //字符串遍历完成,判断栈是否为空
        return stack.isEmpty();
    }
}
